package com.yiwenup.leetcode.offer;

/**
 * https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
 **/
public class No053 {
    /**
     * 执行用时：1 ms, 在所有 Java 提交中击败了28.06%的用户
     * 内存消耗：41.4 MB, 在所有 Java 提交中击败了25.30%的用户
     */
    public int search(int[] nums, int target) {
        int count = 0;
        for (int num : nums) {
            if (num == target) count++;
        }
        return count;
    }


    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：41.5 MB, 在所有 Java 提交中击败了11.67%的用户
     */
    public int search2(int[] nums, int target) {
        int count = 0;
        int idx = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                idx = i;
                break;
            }
        }
        while (idx < nums.length) {
            if (nums[idx++] != target) break;
            count++;
        }
        return count;
    }

    /**
     * 执行用时：1 ms, 在所有 Java 提交中击败了28.06%的用户
     * 内存消耗：41.2 MB, 在所有 Java 提交中击败了74.56%的用户
     */
    public int search3(int[] nums, int target) {
        if (nums.length == 0) return 0;
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            if (nums[left] < target) left++;
            if (nums[right] > target) right--;
            if (nums[left] == nums[right]) break;
        }

        return nums[left] != target ? 0 : right - left + 1;
    }

    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：41.5 MB, 在所有 Java 提交中击败了22.58%的用户
     */
    public int search4(int[] nums, int target) {
        int left = getBound(nums, target);
        int right = getBound(nums, target + 1);
        return left == right ? 0 : right - left;
    }

    public int getBound(int[] nums, int target) {
        int lIdx = 0;
        int hIdx = nums.length - 1;

        while (lIdx <= hIdx) {
            int mIdx = (lIdx + hIdx) >> 1;
            if (nums[mIdx] > target) hIdx = mIdx - 1;
            else lIdx = mIdx + 1;
        }
        return lIdx;
    }
}
